package org.alis.smallcc.josephus;

/** 
* @ClassName: Josephus 
* @Description: 约瑟夫环
* @author: smallcc
* @date 2019年8月6日 下午9:59:19 
*  
*/
public class Josephus {
	// 这个环里面一个有N个人
	private static int N=50;
	// 数到M就杀掉一个人
	private static int M=3;
	
	public static void main(String[] args){
		Josephus j=new Josephus();
//		j.killNode(j.makeNode());
//		for(int i=1;i<=N;i++){
//			System.out.println("第"+i+"次移出去的人是"+j.ysf(N ,M , i));
//		}
//		j.arrayYsf(N,M);
	}
	//killNode
	private void killNode(Node current){
		System.out.println("开始杀人->杀人顺序是:");
		while(current!=current.next){
			// 至少还有两个人就仍然kill
			for(int i=1;i<M;i++){
				current=current.next;
			}
			System.out.println(current.next.val+"被kill掉了");
			// 找下一个受害者
			current.next=current.next.next;
		}
		System.out.println("只有"+current.val+"活了下来");
	}
	// 创建一个链表
	private Node makeNode(){
		// 要杀的第一个人
		Node header=new Node(1);
		// 目前点到的人
		Node current=header;
		for(int i=2;i<=N;i++){
			current=(current.next=new Node(i));
		}
		//首尾相连
		current.next=header;
		return current;
	}
	// 节点
	class Node{
		private int val;
		private Node next;
		public Node(int val){
			this.val=val;
		}
	}
	// 递归实现
	private int ysf(int n,int m,int k){
		if(k==1){
			return (n+m-1)%n+1;
		} else{
	       return (ysf(n-1,m,k-1)+m-1)%n+1;
	    }
	}
	// 数组实现
	private void arrayYsf(int n,int m){
		 /*开始时设置一个长度为总人数的数组，并将元素都设为true start*/
        boolean[] peopleFlags = new boolean[n];
        for (int i = 0; i < n; i++) {
            peopleFlags[i] = true;
        }
        /*开始时设置一个长度为总人数的数组，并将元素都设为true end*/
        int peopleLeft = n; //剩下的人数
        int count = 0; //计数器，每过一个人加一，加到keyNumber时归零
        int index = 0; //标记从哪里开始
        while (peopleLeft > 1) {
            if (peopleFlags[index]) {
                //说明还没有被淘汰 计数器加1
                count++;

                if (count == m) {
                    count = 0; //计数器归0
                    peopleFlags[index] = false; //此人被淘汰
                    peopleLeft--;//未被淘汰的人数-1
                }
            }
            index++;

            //当当前人等于总人数时，则又从第一人开始计数
            if (index == n) {
                index = 0;
            }
        }
      //经过上面的循环，现在数组中被淘汰的人都标记为false，最后没被淘汰都人标记为true
        for (int j = 0; j < n; j++) {
            if (peopleFlags[j]) {
            	  System.out.println(n + "个人围成一圈数数，数到" + m + "的被淘汰，最后剩下的是第" + (j + 1) + "个人。");
            }
        }
	}
}
